package cqu.zhaiyixin20215521.huarondao.slice.huarondaoPlay;

import cqu.zhaiyixin20215521.huarondao.slice.huarondaoPlay.HuaRonDao;

import java.util.Arrays;

public class HuaRonDaoAnswer {
    public final int rowNum;
    public final int colNum;
    public final int[] pieces;
    public final char[] nodes; //每个状态所对应的结点

    public HuaRonDaoAnswer(int rowNum, int colNum) {
        this.rowNum = rowNum;
        this.colNum = colNum;
        pieces = new int[rowNum * colNum];
        for(int i = 0; i < pieces.length; ++i) {
            pieces[i] = i;
        }
        factorials = new int[pieces.length + 1];
        factorials[0] = 1;
        for(int i = 1; i < factorials.length; ++i) {
            factorials[i] = i * factorials[i - 1];
        }
        nodes = new char[factorials[pieces.length]];
        hasShown = new boolean[pieces.length];
    }

    public void init() {
        //求最短路径
        //用BFS遍历所有结点
        int[] queue = new int[factorials[pieces.length]];
        int root = getHashCode();
        queue[0] = root;
        int queueHead = 0; //头指针
        int queueTail = 1; //尾指针
        nodes[root] = '#'; //根结点
        while (queueHead < queueTail) {
            decode(queue[queueHead]);
            int spaceRow, spaceCol, spaceIndex; //空格所在的位置
            for(int i = 0; ; ++i) {
                if(pieces[i] == pieces.length - 1) {
                    spaceRow = i / colNum;
                    spaceCol = i % colNum;
                    spaceIndex = i;
                    break;
                }
            }
            if(0 < spaceRow) { //上
                int pieceIndex = spaceIndex - colNum;
                pieces[spaceIndex] = pieces[pieceIndex];
                pieces[pieceIndex] = pieces.length - 1;
                int hashCode = getHashCode();
                if(nodes[hashCode] == 0) {
                    nodes[hashCode] = 'u';
                    queue[queueTail] = hashCode;
                    queueTail++;
                }
                pieces[pieceIndex] = pieces[spaceIndex];
                pieces[spaceIndex] = pieces.length - 1;
            }
            if(spaceRow + 1 < rowNum) { //下
                int pieceIndex = spaceIndex + colNum;
                pieces[spaceIndex] = pieces[pieceIndex];
                pieces[pieceIndex] = pieces.length - 1;
                int hashCode = getHashCode();
                if(nodes[hashCode] == 0) {
                    nodes[hashCode] = 'd';
                    queue[queueTail] = hashCode;
                    queueTail++;
                }
                pieces[pieceIndex] = pieces[spaceIndex];
                pieces[spaceIndex] = pieces.length - 1;
            }
            if(0 < spaceCol) { //左
                int pieceIndex = spaceIndex - 1;
                pieces[spaceIndex] = pieces[pieceIndex];
                pieces[pieceIndex] = pieces.length - 1;
                int hashCode = getHashCode();
                if(nodes[hashCode] == 0) {
                    nodes[hashCode] = 'l';
                    queue[queueTail] = hashCode;
                    queueTail++;
                }
                pieces[pieceIndex] = pieces[spaceIndex];
                pieces[spaceIndex] = pieces.length - 1;
            }
            if(spaceCol + 1 < colNum) { //右
                int pieceIndex = spaceIndex + 1;
                pieces[spaceIndex] = pieces[pieceIndex];
                pieces[pieceIndex] = pieces.length - 1;
                int hashCode = getHashCode();
                if(nodes[hashCode] == 0) {
                    nodes[hashCode] = 'r';
                    queue[queueTail] = hashCode;
                    queueTail++;
                }
                pieces[pieceIndex] = pieces[spaceIndex];
                pieces[spaceIndex] = pieces.length - 1;
            }
            queueHead++;
        }
    }

    private final int[] factorials; //阶乘表
    private int getHashCode() {
        //华容道的每一种状态可以视作一种排列
        //求排列的字典序
        int hashCode = 0;
        for(int i = 0; i < pieces.length; ++i) {
            int restSmallerNumbersCount = 0; //第i个数在剩余的数当中排第几小
            for(int j = i + 1; j < pieces.length; ++j) {
                if(pieces[j] < pieces[i]) {
                    restSmallerNumbersCount++;
                }
            }
            hashCode += restSmallerNumbersCount * factorials[pieces.length - 1 - i];
        }
        return hashCode;
    }

    private final boolean[] hasShown; //hasShown[i]记录数字i是否已经出现
    private void decode(int hashCode) {
        //根据字典序，转换成华容道
        Arrays.fill(hasShown, false);
        for(int i = 0; i < pieces.length; ++i) {
            int restSmallerNumbersCount = hashCode / factorials[pieces.length - 1 - i];
            hashCode -= restSmallerNumbersCount * factorials[pieces.length - 1 - i];
            //已知number在未出现的数字中第restSmallerNumberCount小，求number是多少
            //解法：从小到大，在未出现的数字中，找第restSmallerNumberCount个数
            int number = -1, smallerNumbersCount = -1;
            do {
                number++;
                if(!hasShown[number]) {
                    smallerNumbersCount++;
                }
            } while(smallerNumbersCount < restSmallerNumbersCount);
            pieces[i] = number;
            hasShown[number] = true;
        }
    }

    public int paceRow;
    public int paceCol;
    public int direction;
    public void next(HuaRonDao huaRonDao) {
        //根据华容道状态，提供最短路径的下一步
        int spaceRow = -1;
        int spaceCol = -1;
        for(int i = 0; i < rowNum; ++i) {
            for(int j = 0; j < colNum; ++j) {
                pieces[i * colNum + j] = huaRonDao.get(i, j);
                if(pieces[i * colNum + j] == pieces.length - 1) {
                    spaceRow = i;
                    spaceCol = j;
                }
            }
        }
        char c = nodes[getHashCode()];
        switch (c) {
            case 'u':
                direction = HuaRonDao.UP;
                paceRow = spaceRow + 1;
                paceCol = spaceCol;
                break;
            case 'd':
                direction = HuaRonDao.DOWN;
                paceRow = spaceRow - 1;
                paceCol = spaceCol;
                break;
            case 'l':
                direction = HuaRonDao.LEFT;
                paceRow = spaceRow;
                paceCol = spaceCol + 1;
                break;
            case 'r':
                direction = HuaRonDao.RIGHT;
                paceRow = spaceRow;
                paceCol = spaceCol - 1;
                break;
            case 0:
                direction = -1; //不可达
                break;
            case '#':
                direction = 0;
                break;
        }
    }

}
